\section{The Fundamentals: Algorithms, the Integers, and Matrices}

\subsection{Algorithms}

\subsubsection{Introduction}

When presented with a problem, construct a model that translates the
problem into a mathematical context. Once we have a mathematical model, we
need a method that will sove the general problem using the model, that
follows a sequence of steps and leads to the desired answer.
\\

\begin{definition}
  An \textit{algorithm} is a finite set of precise instruction for performing a
  computation or for solving a problem.
\end{definition}

\subsubsection{Searching Algorithms}

Linear search (sequential search) and binary search.

\subsubsection{Sorting}

Bubble sort and insertion sort.

\subsubsection{Greedy Algorithms}

Often we want to solve \textit{optimization problems}. One of the simplest
approaches is to select the best choice at each step, instead of
considering all sequences of steps that may lead to an optimal solution.
Algorithms that make what seems to be the ``best'' choice at each step are
called \textit{greedy algorithms}.
Once a greedy algorithm ginds a feasible solution, we need to prove that
it's optimal or we need to find an counterexample.
\\

\begin{example}
  Making changes using pennies, nickels, dimes and quaters.
\end{example}

\begin{lemma}
  \label{lemma:change}
  If $n$ is a postive integer, then $n$ cents in change using quarters, dimes,
  nickels and pennies using the fewest coins possible has at most two dimes, at
  most one nickel, at most for pennies, and cannot have two dimes and a nickel.
  The amount of changes in dimes, nickels, and pennies cannot exceed 24 cents.
\end{lemma}

\begin{proof}
  By contradiction.
\end{proof}

\begin{theorem}
  Greedy is optimal for making changes using quarters, dimes, nickels, and
  pennies.
\end{theorem}

\begin{proof}
  \marginpar{What if we don't have nickels?}
  Suppose the greedy solution uses $q$ quarters and the optimal solution uses
  $q'$ quarters. Then $q'\le q$ because the greedy solution uses the most
  quarters possible. We also have $q'\ge q$ because otherwise, there would be
  at least $25$ cents left the are made up by dimes, nickels and pennies, which
  contradicts Lemma \ref{lemma:change}. Similarly, they use the same number of dimes,
  nickels, and pennies.
\end{proof}

\subsubsection{The Halting Problem}

Undecidable, proof by contradiction.

\subsection{The Growth of Functions}

\subsubsection{Introduction}

We want to estimate the time required by an algorithm to solve a problem, but
we want it to be independent of the underlying hardware doing the computation.
The Big-$O$ notation allows us to estimate the growth of a function without
worrying about constant multiplyer and lower order terms.

\subsubsection{Big-$O$ Notation}

\begin{definition}
  Let $f$ and $g$ be functions from $\mathbb{Z}$ or
  $\mathbb{R}$to $\mathbb{R}$. We say that $f\left(x\right)$ is
  $O\left(g\left(x\right)\right)$ if there are constants $c$ and $k$ such that
  \begin{align*}
    \abs{f\left(x\right)}\le c\abs{g\left(x\right)}
  \end{align*}
  whenver $x>k$.
  \\

  The constants $c$ and $k$ are called \textit{witnesses} to the relationship
  $f\left(x\right)$ is $O\left(g\left(x\right)\right)$. To establish the
  relationship $f\left(x\right)$ is $O\left(g\left(x\right)\right)$, we need
  find only one pair of constants $c$ and $k$ such that
  $\abs{f\left(x\right)}\le c\abs{g\left(x\right)}$ whenever $x>k$.
\end{definition}

\subsubsection{Some Important Big-$O$ Results}

\begin{theorem}
  Let $f\left(x\right)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$,
  where $a_0,\dots,a_n$ are real numbers. Then $f\left(x\right)$ is
  $O\left(x^n\right)$.
\end{theorem}

\begin{proof}
  Using triangle inequality, if $x>1$, we have
  \begin{align*}
    \abs{f\left(x\right)}
    &=\abs{a_nx^n+\cdots+a_1x+a_0}\\
    &\le\abs{a_n}x^n+\cdots+\abs{a_1}x+\abs{a_0}\\
    &=x^n\left(\abs{a_n}+\cdots+\abs{a_1}/x^{n-1}+\abs{a_0}/x^n\right)\\
    &\le x^n\left(\abs{a_n}+\cdots+\abs{a_1}+\abs{a_0}\right).
  \end{align*}
\end{proof}

\begin{example}
  $n!$ is $O\left(n^n\right)$ with witnesses $c=1$ and $k=1$.
  Taking logarithms of both sides:
  \begin{align*}
    n!&\le n^n\\
    \log n!&\le\log n^n\\
    \log n!&\le n\log n.
  \end{align*}
  Therefore, $\log n!$ is $O\left(n \log n\right)$.
\end{example}

Big-$O$ notation is used to estimate the number of operations needed to solve a
problem using an algorithm. The functions used in these estimates often include
the following:
\begin{align*}
  1,\log n,n,n\log n,n^2,2^n,n!
\end{align*}
It can be shown that each function in the list is smaller than the succeeding
function, in the sense that the ratio goes to zero as $n$ goes to infinity.

\subsubsection{The Growth of Combinations of Functions}

If $f_1\left(x\right)=O\left(g_1\left(x\right)\right)$ and
$f_2\left(x\right)=O\left(g_2\left(x\right)\right)$, then
$f_1\left(x\right)+f_2\left(x\right)$ is
$O\left(\max\left(\abs{g\left(x\right)},\abs{g_2\left(x\right)}\right)\right)$,
and $\left(f_1f_2\right)\left(x\right)$ is
$O\left(g_1\left(x\right)g_2\left(x\right)\right)$.

\subsubsection{Big-Omega and Big-Theta Notation}

\begin{definition}
  Let $f$ and $g$ be functions from $\mathbb{Z}$ or $\mathbb{R}$to
  $\mathbb{R}$. We say that $f\left(x\right)$ is
  $\Omega\left(g\left(x\right)\right)$ if there are postive constants $c$ and
  $k$ such that
  \begin{align*}
    \abs{f\left(x\right)}\ge c\abs{g\left(x\right)}
  \end{align*}
  whenever $x>k$.
\end{definition}

\begin{definition}
  Let $f$ and $g$ be functions, we say that $f\left(x\right)$ is
  $\Theta\left(g\left(x\right)\right)$ if $f\left(x\right)$ is
  $O\left(g\left(x\right)\right)$ and $f\left(x\right)$ is
  $\Omega\left(g\left(x\right)\right)$.
\end{definition}

\subsection{Complexity of Algorithms}

\subsection{The Integers and Division}

\subsubsection{Division}

\begin{definition}
  If $a$ and $b$ are integers with $a\ne 0$, we say that $a$ \textit{divides}
  $B$ if there is an integer $c$ such that $b=ac$. When $a$ devides $b$ we say
  that $a$ is a \textit{factor} of $b$ and that $b$ is a \textit{multiple} of
  $a$. The notation $a\mid b$ denotes that $a$ divides $b$. We write $a\not\mid
  b$ when $a$ does not divide $b$.
\end{definition}

\begin{theorem}
  Let $a$, $b$ and $c$ be integers. Then
  \begin{enumerate}[(i)]
    \item if $a\mid b$ and $a\mid c$, then $a\mid \left(b+c\right)$;
    \item if $a\mid b$, then $a\mid bc$ for all integers $c$;
    \item if $a\mid b$ and $b\mid c$, then $a\mid c$.
  \end{enumerate}
\end{theorem}

\begin{corollary}
  If $a$, $b$ and $c$ are integers such that $a\mid b$ and $a\mid c$, then
  $a\mid mb+nc$ whenever $m$ and $n$ are integers.
\end{corollary}

\subsubsection{The Division Algorithm}

When an integer is divided by a positive integer, there is a quotient and a
remainder.
\\

\begin{theorem}[The Division Algorithm]
  Let $a$ be an integer and $d$ a positive integer. Then there are unique
  integers $q$ and $r$, with $0\le r<d$, such that $a=dq+r$.
\end{theorem}

\begin{proof}
  Defered.
\end{proof}

\subsubsection{Modular Arithmetic}

In some situations, we care only about the remainder. For instance, we might
ask what time it will be 50 hours from now.
\\

\begin{definition}
  If $a$ and $b$ are integers and $m$ is a positive integer, then $a$ is
  \textit{congruent to $b$ modulo $m$} if $m$ divides $a-b$. We use the
  notation $a\equiv b\pmod{m}$ to indicate this.
\end{definition}

\begin{theorem}
  Let $a$ and $b$ be integers, and let $m$ be a positive integer. Then $a\equiv
  b\pmod{m}$ iff $a\bmod{m}=b\bmod{m}$.
\end{theorem}

\begin{theorem}
  Let $m$ be a positive integer. The integers $a$ and $b$ are congruent modulo
  $m$ iff there is an integer $k$ such that $a=b+km$.
\end{theorem}

The set of all integers congruent to an integer $a\bmod m$ is called the
\textit{congruence class} of $a\bmod m$.
\\

\begin{theorem}
  Let $m$ be a positive integer. If $a\equiv b\pmod{m}$ and $c\equiv
  d\pmod{m}$, then
  \begin{align*}
    a+c\equiv b+d\pmod{m}
  \end{align*}
  and
  \begin{align*}
    ac\equiv bd\pmod{m}.
  \end{align*}
\end{theorem}

\begin{corollary}
  Let $m$ be a positive integer and let $a$ and $b$ be
  integers. Then
  \begin{align*}
    \left(a+b\right)\bmod m=
    \left( \left( a\bmod m \right)+\left( b\bmod m \right) \right) \bmod m
  \end{align*}
  and
  \begin{align*}
    ab\bmod m=\left( \left( a\bmod m \right)\left( b\bmod m \right) \right) \bmod m.
  \end{align*}
\end{corollary}

Some properties we may expect to be true are not valid. For example, if
$ac\equiv bc\left(\bmod m \right)$, the congruence $a\equiv b\left(\bmod
m\right)$ may be false.

\subsubsection{Applications of Congruences}

Many different hashing functions are used, one of the most common is the
function
\begin{align*}
  h\left(k\right)=k\bmod m
\end{align*}
where $m$ is the number of available memory locations. Hashing functions should
be easily evaluated and also onto, the above function satisfies these
properties.
\\

The most commonly used procedure for generating pseudorandom numbers is the
\textit{linear congruential method}. We choose four integers: the
\textit{modulus} $m$, \textit{multiplier} $a$, \textit{increment} $c$, and
\textit{seed} $x_0$, with $2\le a<m$, $0\le c<m$, and $0\le x_0<m$. We generate
a sequence of pseudorandom numbers $\left\{ x_0 \right\}$, with $0\le x_n<m$
for all $n$, by successively using the congruence
\begin{align*}
  x_{n+1}=\left( ax_n+c \right)\bmod m.
\end{align*}
Many times we want pseudorandom random numbers between $0$ and $1$. To generate
such numbers, we just divide $x_n$ by $m$. Note that this method necessarily
generates sequence that repeats itself.
\\

Often, a linear congruential generator with increment $c=0$ is used. Such a
generator is called a \textit{pure multiplicative generator}. For example, the
pure multiplicative generator with modulus $2^31-1$ and multiplier $7^5=16807$
is widely used. With these values, it can be shown that $2^{31}-2$ numbers are
generated before repetition begins.

\subsubsection{Cryptology}

Congruences have many applications to discrete mathematics and computer
science. One of the most important applications involves \textit{cryptology},
which is the study of secret messages. One of the earliest known uses of
cryptology was by Julius Caesar with his cipher, which is basically an addition
followed by a modulo. Obviously, Caesar's method does not provide a high level
of security. One approach that slightly enhances the security is to use a
function of the form
\begin{align*}
  f\left( p \right)=\left( ap+b \right)\bmod26,
\end{align*}
where $a$ and $b$ are integers, chosen such that $f$ is a bijection.
\\

Caesar's method and its generalizations are vulnerable to attacks based on the
frequency of occurrence of letters in the message.

\subsection{Primes and Greatest Common Divisors}

\subsubsection{Primes}

\begin{definition}
  A positive integer $p$ greater than $1$ is called \textit{prime} if the only
  positive facotrs of $p$ are $1$ and $p$. A postive integer that is greater
  than $1$ and is not prime is called \textit{composite.}
\end{definition}

\begin{theorem}[The Fundamental Theorem of Arithmetic]
  Every positive integer greater than $1$ can be written uniquely as a prime or
  as the product of two or more primes where the prime factors are written in
  order of nondecreasing size.
\end{theorem}

\begin{theorem}
  If $n$ is a composite integer, then $n$ has a prime divisor less than or
  equal to $\sqrt{n}$.
\end{theorem}

\begin{theorem}
  There are infinitely many primes.
\end{theorem}

\begin{proof}
  Suppose that there are only finitely many primes,
  $p_1,p_2,\dots,p_n$. Let
  \begin{align*}
    Q=p_1p_2\cdots p_n+1.
  \end{align*}
  By the fundamental theorem of arithmetic, $Q$ is prime or else it can be
  written as the product of two or more primes. However, none of the primes
  $p_j$ divides $Q$, for if $p_j\mid Q$, then $p_j$ divides $Q-p_1\cdots
  p_n=1$. Hense, there is a prime not in the list $p_1,\dots,p_n$. This prime
  is either $Q$, if it is prime, or a prime factor of $Q$. This is a
  contradiction.
\end{proof}

Note that this proof does not state that $Q$ is prime! This is a
nonconstructive existence proof.
\\

For many years, the largest prime known has been an integer of the special form
$2^p-1$ where $p$ is also prime. Such primes are called \textit{Mersenne
primes}, because there is an extremely efficient test, known as the
Lucas-Lehmer test, for determining whether $2^p-1$ is prime.
\\

\begin{theorem}[The prime number thoerem]
  The ratio of the number of primes not exceeding $x$ and $x/\ln x$ approaches
  $1$ as $x$ grows without bound.
\end{theorem}

Therefore, the odds that a randomly chosen integer less than $n$ are
approximaltely $1/\ln n$. Using calculus, it can be shown that the probability
that an integer $n$ is prime is also approximaltely $1/\ln n$.

\subsubsection{Conjectures and Open Problems About Primes}

\textit{Goldbach's Conjecture:} Every even integer $n$, $n>2$, is the sum of two
primes.
\\

\textit{The Twin Prime Conjecture:} Twin primes are the primes that differ by
$2$. The twin prime conjecture asserts that there are infinitely many twin
primes.

\subsubsection{Greatest Common Divisors and Least Comman Mutiples}

\begin{definition}
  Let $a$ and $b$ be integers, not both zero. The largest integer $d$ such that
  $d\mid a$ and $d\mid b$ is called the \textit{greatest common divisor} of $a$
  and $b$. The greatest common divisor of $a$ and $b$ is denoted by
  $\text{gcd}\left( a,b \right)$.
\end{definition}

\begin{definition}
  The integers $a$ and $b$ are \textit{relatively prime} if their greatest
  common divisor is 1.
\end{definition}

\begin{definition}
  The integers $a_1,a_2,\dots,a_n$ are \textit{pairwise relatively prime} if
  $\text{gcd}\left( a_i,a_j \right)=1$ whenever $1\le i<j\le n$.
\end{definition}

\begin{definition}
  The \textit{least common multiple} of the positive integers $a$ and $b$ is
  the smallest positive integer that is divisible by both $a$ and $b$, denoted
  by $\text{lcm}\left( a,b \right)$.
\end{definition}

\begin{theorem}
  Let $a$ and $b$ be positive integers. Then
  \begin{align*}
    ab=\text{gcd}\left( a,b \right)\cdot\text{lcm}\left( a,b \right).
  \end{align*}
\end{theorem}

\subsection{Integers and Algorithms}

\subsubsection{Representations of Integers}

\begin{theorem}[Base $b$ expansion of integers]
  Let $b$ be a positive integer greater than $1$. Then if $n$ is a positive
  integer, it can be expressed uniquely in the form
  \begin{align*}
    n=a_kb^k+a_{k-1}b^{k-1}+\cdots+a_1+b+a_0
  \end{align*}
  where $k$ is a nonnegative integer, $a_0,a_1,\dots,a_k$ are nonnegative
  integers less than $b$ and $a_k\ne0$.
\end{theorem}

This is called the \textit{base $b$ expansion of $n$}, and is denoted by
$\left( a_ka_{k-1}\dots a_1a_0 \right)_b$. We give an algorithm for finding the
base $b$ expansion of any positive integer:
\\

\rule{\linewidth}{0.7pt}
Given a positive integer $n$:\\
$k\gets 0$\\
\textbf{while} $n\neq0$:\\
\tab$a_k\gets n\bmod b$\\
\tab$n\gets\floor{n/b}$\\
\tab$k\gets k+1$\\
The base $b$ expansion of $n$ is $\left( a_{k-1}\dots a_1a_0 \right)_b$.\\
\rule{\linewidth}{0.7pt}

\subsubsection{Algorithms for Integer Operations}

To perform multiplication, have a loop that left shifts one of the number and
compute the product by adding up the number being shifted, according to the
other number. Division can be done as successive substraction untill the
remainder is less than the divisor.\\

Surprisingly, there are more efficient algorithms than the conventional
algorithm for multiplication. One such algorithm, which uses $O\left( n^{1.585}
\right)$ bit operations to multiply $n$-bit numbers, will be described in
Section $7.3$. Similarly, there exists $O\left( \log a\log d \right)$
algorithms for computing $a/d$.

\subsubsection{Modular Exponentiation}

In cryptography it is important to be able to find $b^n\bmod{m}$ efficiently,
where $b$, $n$ and $m$ are large integers. It is impratical to first compute
$b^n$ and then find its remainder when divided by $m$. We will use a better
algorithm.
\\

Using the binary expansion of $n$, we note that
\begin{align*}
  b^n=b^{a_{k-1}2^{k-1}+\cdots+a_12+a_0}=b^{a_{k-1}2^{k-1}}\cdots
  b^{a_12}b^{a_0}.
\end{align*}
To compute $b^n$, we find the values of $b,b^2,\left( b^2
\right)^2=b^4,\dots,b^{2^k}$. Next, we multiply the terms $b^{2^j}$ in this
list, where $a_j=1$. This gives us $b^n$.\\

The algorithm successively finds $b\bmod{m}$, $b^2\bmod m$, $b^4\bmod
m$,\ldots, $b^{2^{k-1}}\bmod m$ and multiplies together those terms when
$a_j=1$, finding the remainder of the product when divided by $m$ after each
multiplication.\\

\rule{\linewidth}{0.7pt}
Given integers $b$, $n=\left( a_{k-1}a_{k-2}\dots a_1a_0 \right)_2$ and $m$.\\
$x\gets 1$\\
$p\gets b\bmod m$\\
\textbf{for} $i\gets 0$ upto $k-1$\\
\tab\textbf{if} $a_i=1$ \textbf{then} $x\gets\left( x\cdot p \right)\bmod m$\\
\tab$p\gets\left( p^2 \right)\bmod m$\\
We have that $b^n\bmod m$.\\
\rule{\linewidth}{0.7pt}\\

Loop invariant: in the $i$-th iteration, $x=b^{\left(a_{i-1}\dots
a_0\right)_2}\bmod m$ and $p=b^{2^i}\bmod m$.  Also note that $ab\bmod
c=a\left( b\bmod c \right)\bmod c$.
\\

This algorithm uses $O\left( \left( \log m \right)^2\log n \right)$ bits
operations to find $b^n\bmod m$ (see Exercise 56).

\subsubsection{The Euclidean Algorithm}

The Euclidean algorithm finds the greatest common divisor, it's mainly based on
the following lemma:\\

\begin{lemma}
  Let $a=bq+r$ where $a,b,q$ and $r$ are integers. Then $\text{gcd}\left( a,b
  \right)=\text{gcd}\left( b,r \right)$.\\
\end{lemma}

It turns out that the Euclidean Algorithm for calculating $\text{gcd}\left(
a,b \right)$ has time complexity $O\left( \log b \right)$.

\subsection{Applications of Number Theory}

\subsubsection{Some Useful Results}

\begin{theorem}
  If $a$ and $b$ are positive integers, then there exist integers $s$ and $t$
  such that $\text{gcd}\left( a,b \right)=sa+tb$.
\end{theorem}

For more see the notes from the exercises.
\\

\begin{lemma}
  If $a$, $b$ and $c$ are positive integers such that $\text{gcd}\left( a,b
  \right)=1$ and $a\mid bc$, then $a\mid c$.
\end{lemma}

\begin{proof}
  Because $\text{gcd}\left( a,b \right)=1$, there are integers
  $s$ and $t$ such that
  \begin{align*}
    sa+tb=1.
  \end{align*}
  Multiply both sides by $c$, we obtain
  \begin{align*}
    sac+tbc=c.
  \end{align*}
  Since $a\mid bc$, we have that $a\mid tbc$, thus $a\mid sac+tbc=c$.
\end{proof}

\begin{lemma}
  If $p$ is a prime and $p\mid a_1a_2\cdots a_n$, where each $a_i$ is an
  integer, then $p\mid a_i$ for some $i$.
\end{lemma}

\begin{proof}[Proof (of the uniqueness of the prime factorization, one
  direction of the proof for the fundamental theorem of arithmetic]
  Suppose, for a contradiction, that the positive integer $n$ can be written as
  the product of primes in two different ways, say, $n=p_1p_2\cdots p_s$ and
  $n=q_1q_2\cdots q_t$, each $p_i$ and $q_j$ are primes in nondecreasing order.
  Remove all common primes from the two factorization, we have
  \begin{align*}
    p_{i_1}p_{i_2}\cdots p_{i_u}=q_{j_1}q_{j_2}\cdots q_{j_v},
  \end{align*}
  where no prime occurs on both sides and $u$ and $v$ are positive integers. By
  the above lemma, $p_{i_1}$ divides $q_{j_k}$ for some $k$. Because no prime
  divides another prime, this is impossible.
\end{proof}

\begin{theorem}
  \label{thm2}
  Let $m$ be a positive integer and let $a$, $b$ and $c$ be integers. If
  $ac\equiv bc\pmod{m}$ and $\text{gcd}\left( c,m \right)=1$, then
  $a\equiv b\pmod{m}$.
\end{theorem}

\begin{proof}
  Because $ac\equiv bc\pmod{m}$, $m\mid ac-bc=c\left( a-b
  \right)$. By one of the previous lemma, because $\text{gcd}\left( c,m
  \right)=1$, it follows that $m\mid a-b$, thus $a\equiv b\pmod{m}$.
\end{proof}

\subsubsection{Linear Congruences}

A congruence of the form
\begin{align*}
  ax\equiv b\pmod{m},
\end{align*}
where $x$ is a variable, is called a \textit{linear congruence}. 
\\

How do we solve linear congruences? That is, find all integer $x$ that satisfy
this congruence?
One method uses an integer $\bar{a}$ such that $\bar aa\equiv 1\pmod{m}$, if
such an integer exists.
Such an integer $\bar a$ is said to be an \textit{inverse} of $a$ modulo $m$.
\\

\begin{theorem}
  If $a$ and $m$ are relatively prime and $m>1$, then an inverse of $a$ modulo
  $m$ exists and is unique.
\end{theorem}

\begin{proof}
  Since $\text{gcd}\left( a,m \right)=1$, there are integers $s$ and $t$ such
  that
  \begin{align*}
    sa+tm=1.
  \end{align*}
  This implies that
  \begin{align*}
    sa+tm\equiv 1\pmod{m}.
  \end{align*}
  Because $tm\equiv 0\pmod{m}$, it follows that
  \begin{align*}
    sa\equiv 1\pmod{m}.
  \end{align*}
  So $s$ is an inverse of $a$ modulo $m$. The uniqueness is left as Exercise 9
  at the end of this section.
\end{proof}

\begin{example}
  Solve $3x\equiv 4\pmod{7}$. First $-2$ is an inverse of 3 modulo 7:
  \begin{align*}
    3x&\equiv 4\pmod{7}\\
    -2\cdot3x&\equiv -2\cdot4\pmod{7}.
  \end{align*}
  Since $-6\equiv 1\pmod{7}$ and $-8\equiv 6\pmod{7}$, it follows that if $x$
  is a solution, then $x\equiv -8\equiv6\pmod{7}$.
\end{example}

\subsubsection{The Chinese Remainder Theorem}

\begin{theorem}[The Chinese Remainder Theorem]
  Let $m_1,m_2,\dots,m_n$ be pairwise relatively prime and $a_1,a_2,\dots,a_n$
  be arbitrary integers. Then the system
  \begin{align*}
    x&\equiv a_1\pmod{m_1},\\
    x&\equiv a_2\pmod{m_2},\\
    &\vdots\\
    x&\equiv a_n\pmod{m_n}\\
  \end{align*}
  has a unique solution modulo $m=m_1m_2\cdots m_n$. That is, there is a
  solution $x$ with $0\le x<m$, and all other solutions are congruent modulo
  $m$ to this solution.
\end{theorem}

\begin{proof}
  The proof for uniqueness modulo $m$ is left as Exercise 24. To construct a
  simultaneous solution, first let
  \begin{align*}
    M_k=m/m_k
  \end{align*}
  for $k=1,2,\dots,n$. It follows that $\text{gcd}\left( m_k,M_k \right)=1$.
  Therefore there is an integer $y_k$, an inverse of $M_k$ modulo $m_k$, such
  that
  \begin{align*}
    M_ky_k\equiv 1\pmod{m_k}.
  \end{align*}
  Form the sum
  \begin{align*}
    x=a_1M_1y_1+a_2M_2y_2+\cdots+a_nM_ny_n.
  \end{align*}
  Note that
  \begin{align*}
    x\equiv a_kM_ky_k\equiv a_k\pmod{m_k}.
  \end{align*}
\end{proof}

\subsubsection{Computer Arithmetic with Large Integers}

Suppose that $m_1,m_2,\dots,m_n$ are pairwise relatively prime integers greater
than or equal to 2 and let $m$ be their product. By the Chinese Remainder
Theorem, we can show (Exercise 22) that an integer $a$ with $0\le a< m$ can be
uniquely represented by the $n$-tuple consisting of its remainders upon
division by $m_i$, $i=1,2,\dots,n$. That is, we can uniquely represent $a$ by
\begin{align*}
  \left( a\bmod{m_1},a\bmod{m_2},\dots,a\bmod{m_n}\right).
\end{align*}

\begin{example}
  To represent nonnegative integers less than 12, using 3 and 4 as moduli:
  \begin{align*}
    0&=\left( 0,0 \right)\;\;4&=\left( 1,0 \right)\;\;8&=\left( 2,0 \right)\\
    1&=\left( 1,1 \right)\;\;5&=\left( 2,1 \right)\;\;9&=\left( 0,1 \right)\\
    2&=\left( 2,2 \right)\;\;6&=\left( 0,2 \right)\;\;10&=\left( 1,2 \right)\\
    3&=\left( 0,3 \right)\;\;7&=\left( 1,3 \right)\;\;11&=\left( 2,3 \right).
  \end{align*}
\end{example}

This can be use to perform arithmetic with integers larger than can be carried
out on a computer. It also allows parallel computation.
\\

Integers of the form $2^k-1$ where $k$ is a positive integer are good choices
for moduli, because it's easy to do binary arithmetic modulo such integers, and
becuase it's easy to find sets of such integers that are pairwise relatively
prime($\mathrm{gcd}\left( 2^a-1,2^b-1 \right)=2^{\mathrm{gcd}\left( a,b
\right)}-1$, see Exercise 41). Once we have selected the moduli, we carry out
arithmetic operations with large integers by performing compnentwise operations
on the $n$-tuples representing the large integers, all modulo $m_i$. Then we
solve a system of congruence to obtain the answer.
\\

\begin{example}
  Using the moduli 99, 98, 97 and 95, we represent 123684 as $\left( 33,8,9,89
  \right)$ and 413456 as $\left( 32,92,42,16 \right)$.
  \begin{align*}
    \left( 33,8,9,89 \right)+\left( 32,92,42,16 \right)
    &=\left( 65\bmod{99},100\bmod{98},51\bmod{97},105\bmod{95} \right)\\
    &=\left( 65,2,51,10 \right).
  \end{align*}
  We then solve the system of congruences
  \begin{align*}
    x&\equiv65\pmod{99}\\
    x&\equiv2\pmod{98}\\
    x&\equiv51\pmod{97}\\
    x&\equiv10\pmod{95}
  \end{align*}
\end{example}

\subsubsection{Pseudoprimes}

Recall that an integer $n$ is prime when it is not divisible by anpy prime
$p\le\sqrt{n}$.
\\

\begin{theorem}[Fermat's Little Theorem]
  If $p$ is prime and $a$ is an integer not divisible by $p$, then
  \begin{align*}
    a^{p-1}\equiv1\pmod{p}.
  \end{align*}
  Furthermore, for every integer $a$ we have
  \begin{align*}
    a^p\equiv a\pmod(p).
  \end{align*}
\end{theorem}

The proof is outlined in Exercise 17.
\\

Given a positive integer $n$, testing whether $2^{n-1}\equiv1\pmod{n}$ (or some
other base $b\ne2$) is useful because if it passes the test, then $n$ is either
prime or a pseudoprime to the base $2$ (otherwise it's composite), and there
are relatively few pseudoprime than primes. Unfortunately, we cannot
distinguish between primes and pseudoprime by testing in sufficiently many
bases, because there are composite integers $n$ that passes all tests with
bases $\text{gcd}\left( b,n \right)=1$. This leads to the next definition.
\\

\begin{definition}
  Let $b$ be a positive integer. If $n$ is a composite postive integer, and
  $b^{n-1}\equiv1\pmod{n}$, then $n$ is called a \textit{pseudoprime to the
  base $b$}.
\end{definition}

\begin{definition}
  A composite integer $n$ that satisfies the congruence
  $b^{n-1}\equiv1\pmod{n}$ for all postive integers $b$ with $\text{gcd}\left(
  b,n \right)=1$ is called a \textit{Carmichael number}.
\end{definition}

For example, 561 is a Carmichael number.

\subsubsection{The RSA Cryptosystem}

The RSA cryptosystem uses public key cryptography: known how to send someone a
message does not help you decrypt messages sent to this person.
The RSA cryptosystem is based on modular exponentiation modulo the product of
two large primes. Each party has an encryption key $n=pq$, where $p$ and $q$
are large primes, and an exponent $e$ that is relatively prime to $\left( p-1
\right)\left( q-1 \right)$. To produce a usable key, we need to large primes.
This can be done quickly. However, if only given $n$, we can't factor it to get
$p$ and $q$ in a reasonable length of time.

\subsubsection{RSA Encryption}

Massages are translated into sequences of integers. The encryption transform
the integer $M$, representing the original message, to an integer $C$,
representing the encrypted message, using the function
\begin{align*}
  C=M^e\bmod{n}.
\end{align*}

\subsubsection{RSA Decryption}

We use the decryption key $d$, an inverse of $e$ modulo $\left( p-1
\right)\left( q-1 \right)$ (such an inverse exsists becuase $e$ is relatively
prime to $\left( p-1 \right)\left( q-q \right)$). Note that if
$de\equiv1\pmod{\left( p-1 \right)\left( q-1 \right)}$, there is an integer $k$
such that $de=1+k\left( p-1 \right)\left( q-1 \right)$. It follows that
\begin{align*}
  C^d\equiv\left( M^e \right)^d=M^{de}=M^{1+k\left( p-1 \right)\left( q-1
  \right)}\pmod{n}.
\end{align*}
By Fermat's Little Theorem (assuming that $\text{gcd}\left( M,p
\right)=\text{gcd}\left( M,q \right)=1$, which holds except in rare cases), it
follows that $M^{p-1}\equiv1\pmod{p}$ and $M^{q-1}\equiv1\pmod{q}$.
Consequently,
\begin{align*}
  C^d\equiv M\cdot\left( M^{p-1} \right)^{k\left( q-1 \right)}
  \equiv M\cdot 1\equiv M\pmod{p}
\end{align*}
and
\begin{align*}
  C^d\equiv M\cdot\left( M^{q-1} \right)^{k\left( p-1 \right)}
  \equiv M\cdot 1\equiv M\pmod{q}.
\end{align*}
Since $\text{gcd}\left( p,q \right)=1$, it follows by the Chinese Remainder
Theorem that
\begin{align*}
  C^d\equiv M\pmod{pq}.
\end{align*}

\subsection{Additional Notes from Exercise}

We can extend big-$O$, big-Theta, and big-Omega to multivariable functions. For
example, the statement $f\left(x,y\right)$ is $O\left(g\left(x,y\right)\right)$
means that there exists constants $c$, $k_1$ and $k_2$ such that
$\abs{f\left(x,y\right)}\le c\abs{g\left(x,y\right)}$ whenever $x>k_1$ and
$y>k_2$.
\\

Another type of asymptotic notation. We say that $f\left(x\right)$ is
$o\left(g\left(x\right)\right)$ when
\begin{align*}
  \lim_{x\to\infty}\frac{f\left(x\right)}{g\left(x\right)}=0.
\end{align*}
\\

The value of the \textit{Euler $\phi$-function} at the postive integer $n$ is
defined to be the number of positive integers less than or equal to $n$
that are relatively prime to $n$.
\\

It can be shown that every integer can be uniquely represented in the form
\begin{align*}
  e_k3^k+e^{k-1}3^{k-1}+\cdots+e_13+e_0,
\end{align*}
where $e_j=-1,0,\text{or }1$. Expansion of this type are called
\textit{balanced ternary expansion}.
\\

A \textit{Cantor expansion} is a sum of the form
\begin{align*}
  a_nn!+a_{n-1}\left( n-1 \right)!+\cdot+a_22!+a_11!,
\end{align*}
where $a_i$ is an integer with $0\le a_i\le i$ for $i=1,2,\dots,n$.

